package com.zdp.leetcodeMiddle;


import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
*
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 单词拆分_139 {
    public static void main(String[] args) {
        单词拆分_139 demo = new 单词拆分_139();
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        wordDict.add("a");
        boolean leetcode = demo.wordBreak1("aleetcode", wordDict);
        System.out.println(leetcode);
    }

    /*
    * 解题思路：  首先 字符串s 中可以插入多个空格 插入空格的个数，位置的不同，拆分成的单词也不同
    *  可以每次 只拆一个单词呀
    *
    * */
    public boolean wordBreak(String s, List<String> wordDict) {
        //
        int maxLength = 0;
        for(String t : wordDict){
            maxLength = Math.max(maxLength,t.length());
        }
        return f(s,0,s.length(),wordDict,maxLength);

    }

    /*
    * 超时了
    * */
    private boolean f(String s,int start,int end,List<String>wordDict,int maxLength){
        if(start>=end){
            return true;
        }
        StringBuilder temp = new StringBuilder();
        boolean result = false;
        for(int i=start;!result &&  i < end;i++){
            if(end-i+1 > maxLength){
                break;
            }
            temp.append(s.charAt(i));
            if(wordDict.contains(temp.toString())){
                result = f(s,i+1,end,wordDict,maxLength);
            }
        }
        return result;
    }

    /*
     * 使用动态规划  dp[i] 表示：以i元素为结尾的字符串s 是否可以被 wordDict的单词组成
     * dp[i] = dp[j-1] && s[j...i]属于wordDict
     * 而这个 j...i字符串 需要遍历一下得到
     * */
    public boolean wordBreak1(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()];
        dp[0] = wordDict.contains(s.substring(0,1));
        int length = s.length();
        for(int i=1;i<length;i++){
            for(int j = 0;j<=i;j++){
                if( j == 0){
                    if(wordDict.contains(s.substring(j,i+1))){
                        dp[i] = true;
                        break;
                    }
                    continue;
                }

                if(dp[j-1] && wordDict.contains(s.substring(j,i+1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[length-1];
    }

    /*
    * 可以再优化一下
    * dp[i] : 表示以i-1字符结尾的字符串 是否可以分隔
    * dp[i] = dp[j] && s[j...i-1]
    * 还可以进行剪枝：记录wordDict 里面单词的最大长度
    * */
    public boolean wordBreak2(String s, List<String> wordDict) {
        int length = s.length();
        int maxLength = 0;
        for(String t: wordDict){
            maxLength = Math.max(maxLength,t.length());
        }
        boolean[] dp = new boolean[length+1];
        dp[0] = true; // 当j ==0 时，dp[i]是否可以分隔，其实就是看 s[0..i-1]是否在wordDict里面即可，与dp[j]无关了
        for(int i = 1;i<=length;i++){
            for(int j =i-1;j>=0 && j>=i-maxLength;j--){
                if(dp[j] && wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[length];
    }
}
